package com.zlk.algorithm.huawei.leetcode.array;

/**
 * @program: algorithm
 * @ClassName Code07_maxSubArray
 * @description:
 * 给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组
 * （子数组最少包含一个元素），返回其最大和。
 * 子数组
 * 是数组中的一个连续部分。
 * @author: slfang
 * @create: 2025-01-02 17:09
 * @Version 1.0
 **/
public class Code07_maxSubArray {

    public int maxSubArray(int[] nums) {
        // dp 0-i范围上 最大大和的连续子数组 的和
        return f1(nums);
    }

    /**
     * 代表以第 i 个数结尾的「连续子数组的最大和」
     *   dp[i]  dp[i-1]>0依赖前面位置
     *          dp[i-1]<=0 不依赖前面位置
     *
     * @param nums
     * @return
     */
    private int f1(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        int ans = dp[0];
        for (int i = 1; i <n ; i++) {
            dp[i]=dp[i-1]>0?dp[i-1]+nums[i]:nums[i];
            ans = Math.max(dp[i],ans);
        }
        return ans;
    }

}
